# 剑指 Offer 40. 最小的 K 个数
# 一、题目描述
输入整数数组 arr ，找出其中最小的 k 个数。例如，输入 4、5、1、6、2、7、3、8 这 8 个数字，则最小的 4 个数字是 1、2、3、4 。
示例 1：
输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]
示例 2：
输入：arr = [0,1,2,1], k = 1
输出：[0]
限制：
0 <= k <= arr.length <= 100000 <= arr[i] <= 10000
# 二、题目解析
这道题目最简单粗暴的方法当然是将数组 arr 按照从小到大的顺序整体排序之后，获取数组的前 k 个数就行。
而整体排序的算法有很多种选择，比如冒泡、选择、快速、堆排序等等。
这种暴力解法肯定不是面试官想要的回答，因为我们没有利用好题目的全部条件。
再读一下这句话：找出其中最小的 k 个数。
这句话隐藏着以下几个意思：
- 1、找出的这 k 个数并不需要按照顺序排列。
- 2、如果一开始就知道某个数不在这 k 个数中，完全可以将它丢到一旁。
也就意味着，在排序过程中，我们可以去不断的缩小排序的区间，这里我们借助快速排序的代码，稍微的改动几行就完成了这道题目。
具体操作如下：
- 1、以当前区间的第一个元素为基准元素
pivot，根据快速排序的操作，将当前区间划分为了三个区间。 - 1、左侧区间均是小于等于基准元素
pivot的元素 - 2、中间区间均是等于基准元素
pivot的元素 - 3、右侧区间均是大于等于基准元素
pivot的元素
- 1、左侧区间均是小于等于基准元素
- 2、对比基准元素
pivot所在的下标 index 与 k 的关系 - 1、index 小于 k，说明从 0 到 index 这个左侧区间中的元素不足 k 个，那么最小的
k个数肯定部分是在这个区间，还需要继续在右侧区间中去寻找出一部分元素来填充，因此对对右侧区间进行快速排序即可 - 2、index 等于 k，说明从 0 到 index 这个区间中的所有元素就是那些最小的
k个数，将其返回。 - 3、index 大于 k，说明从 0 到 index 这个左侧区间中的元素超过了 k 个，那么最小的
k个数肯定是都在在这个区间，而中间、右侧区间均可以不去处理，只需要继续对左侧区间进行快速排序即可，找到那 k 个数。
- 1、index 小于 k，说明从 0 到 index 这个左侧区间中的元素不足 k 个，那么最小的
# 三、参考代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 剑指 Offer 40. 最小的k个数：https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
if (k == 0 || arr.length == 0) {
return new int[0];
}
// 执行快速排序操作，定位找到下标为 k - 1 的那个元素
return quickSort(arr,0,arr.length - 1,k - 1);
}
// 函数传入待排序数组 nums
// 排序区间的左端点 left
// 排序区间的右端点 right
private int[] quickSort(int[] nums,int left, int right , int index){
// 调用函数 partition，将 left 和 right 之间的元素划分为左右两部分
int mid = partition(nums,left,right);
// 如果 mid 下标恰巧为 index，那么找到了最小的 k 个数
if (mid == index) {
// 直接返回
return Arrays.copyOf(nums, mid + 1);
// 如果 mid 下标大于 index，那么说明需要在左侧元素中去切分
}else if( mid > index ){
// 对 mid 左侧的元素进行快速排序
return quickSort(nums,left,mid - 1, index );
}else{
// 对 mid 右侧的元素进行快速排序
return quickSort(nums,mid + 1,right, index );
}
}
private int partition(int[] nums, int left ,int right){
// 经典快速排序的写法
// 设置当前区间的第一个元素为基准元素
int pivot = nums[left];
// left 向右移动，right 向左移动，直到 left 和 right 指向同一元素为止
while( left < right ){
// 只有当遇到小于 pivot 的元素时，right 才停止移动
// 此时，right 指向了一个小于 pivot 的元素，这个元素不在它该在的位置上
while( left < right && nums[right] >= pivot ){
// 如果 right 指向的元素是大于 pivot 的，那么
// right 不断的向左移动
right--;
}
// 将此时的 nums[left] 赋值为 nums[right]
// 执行完这个操作，比 pivot 小的这个元素被移动到了左侧
nums[left] = nums[right];
// 只有当遇到大于 pivot left 才停止移动
// 此时，left 指向了一个大于 pivot 的元素，这个元素不在它该在的位置上
while( left < right && nums[left] <= pivot){
// 如果 left 指向的元素是小于 pivot 的，那么
// left 不断的向右移动
left++;
}
// 将此时的 nums[right] 赋值为 nums[left]
// 执行完这个操作，比 pivot 大的这个元素被移动到了右侧
nums[right] = nums[left];
}
// 此时，left 和 right 相遇，那么需要将此时的元素设置为 pivot
// 这个时候，pivot 的左侧元素都小于它，右侧元素都大于它
nums[left] = pivot;
// 返回 left
return left;
}
}
# 算法的复杂度分析
空间复杂度 O(1)，不需要额外空间。
时间复杂度的分析方法和快速排序类似。由于快速选择只需要递归一边的数组，时间复杂度小于快速排序，期望时间复杂度为 O(n)，最坏情况下的时间复杂度为 O(n^2)。